package cn.zhaoyuening.algorithms.dynamic;

/**
 * Created by Buynow on 2017/8/12.
 * 最长公共子序列
 */
public class LCS {
    public static void handler(String s1, String s2) {
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        for (int i=1;i<=s1.length();i++) {
            for (int j=1;j<=s2.length();j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                }
            }
        }

        System.out.println(dp[s1.length()][s2.length()]);
    }

    public static void main(String[] args) {
        String s1 = "1A2C3D4B56";
        String s2 = "B1D23CA45B6A";

        handler(s1,s2);
    }
}
